package com.example.demo.leetcode.zuocheng.btree;


import java.util.LinkedList;

/**
 *
 * 判断条件(通过层序遍历):
 *     (1)右边孩子不为空，左孩子为空 返回false
 *     (2)继续判断, 一旦遇到左右孩子不双全，后续遇到的所有节点必须是叶子节点
 *
 */
public class Btree_完全二叉树 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }


    public static boolean isCompleteTree(TreeNode node){

        LinkedList<TreeNode> list = new LinkedList<>();

        boolean leaf = false; //是否遇到过 左右孩子有一个为空的节点
        list.add(node);
        while(!list.isEmpty()){
            TreeNode poll = list.poll();
            TreeNode left = poll.left;
            TreeNode right = poll.right;


            if( (right != null && left==null) || (leaf && (right!=null || left != null))){
                return false;
            }
            if(left == null || right == null){
                leaf = true;
            }

            if(left != null){
                list.add(left);
            }
            if(right != null){
                list.add(right);
            }

        }
        return true;

    }



    public static void main(String [] args){

    }


}
